package algorithms.a03sortadvance;

import algorithms.a02sortbasic.InsertionSort;
import algorithms.a02sortbasic.ShellSort;
import algorithms.utis.SortTestHelper;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author 王昊然
 * @create 2018-02-06 11:39
 **/
public class MergeSort {

    /**
     * 自顶向下的归并排序
     *
     * @param arr
     * @date: 2018/2/6 16:10
     * @author: 王昊然
     */
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        mergeSort(arr, 0, n - 1);//参数是下标
    }

    private static void mergeSort(Comparable[] arr, int left, int right) {

        /*if (left >= right) {
            return;
        }*/
        //在数组片段长度很小的时候，采用插入排序处理，进一步优化速度
        if (right - left < 15) {
            InsertionSort.sort(arr, left, right);
            return;
        }

        int middle = (right + left) / 2;
        mergeSort(arr, left, middle);//参数是下标
        mergeSort(arr, middle + 1, right);

        if (arr[middle].compareTo(arr[middle + 1]) < 0)
            return;//如果中间左侧的已经比右侧小，说明已经是一个排好序的数组片段，不需要再归并

        mergeByTwoOrdererParts(arr, left, middle, right);

    }

    /**
     * 二分后，两部分各自都已经是排序好的数组情况下，整体进行合并
     * 注意，middle并不一定非要代表中间的下标，只要理解为两个数组段的连接位置即可，特别在由下到上的归并中
     *
     * @param arr
     * @param left
     * @param middle
     * @param right
     */
    private static void mergeByTwoOrdererParts(Comparable[] arr, int left, int middle, int right) {


        Comparable[] arrClone = Arrays.copyOfRange(arr, left, right + 1);
        int i = 0;
        middle = middle - left;//转为clone数组的中间位置下标
        int j = middle + 1;

        for (int k = left; k <= right; k++) {

            if (i > middle) {
                arr[k] = arrClone[j];
                j++;
            } else if (j > arrClone.length - 1) {
                arr[k] = arrClone[i];
                i++;

            } else if (arrClone[i].compareTo(arrClone[j]) < 0) {
                arr[k] = arrClone[i];
                i++;
            } else {
                arr[k] = arrClone[j];
                j++;
            }
        }
    }


    public static void sortBottomToUp(Comparable[] arr) {

        int n = arr.length;

        //最小归并单位是两个元素，即中间位置halfSize = 1;分组15个元素以内时用插入排序
        for (int i = 0; i < n; i += 16) {
            InsertionSort.sort(arr, i, Math.min(i + 15, n - 1));
        }


        //最小归并单位是两个元素，即中间位置halfSize = 16;
        for (int halfSize = 16; halfSize < n; halfSize += halfSize) {

            for (int i = 0; i + halfSize < n; i += halfSize + halfSize) {

                int middle = i + halfSize - 1;

                if (arr[middle].compareTo(arr[middle + 1]) < 0)
                    return;//如果中间左侧的已经比右侧小，说明已经是一个排好序的数组片段，不需要再归并

                int right = i + 2 * halfSize - 1;
                if (right > n - 1) right = n - 1;

                mergeByTwoOrdererParts(arr, i, middle, right);
            }
        }
    }


    public static void main(String[] args) {
        int N = 13000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 300000); //1排序数组数值范围小，插入排序优势明显
//        Integer[] arr = new Integer[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        Integer[] arr4 = Arrays.copyOf(arr, arr.length);
        Integer[] arr5 = Arrays.copyOf(arr, arr.length);

        System.out.print("忽略--------");
        SortTestHelper.testSort(InsertionSort.class, arr);
        SortTestHelper.testSort(ShellSort.class, arr);
        SortTestHelper.testSort(MergeSort.class, arr);
        SortTestHelper.testSort(MergeSort.class, arr, "sortBottomToUp");
        System.out.println("----------");

        SortTestHelper.testSort(InsertionSort.class, arr2);
        SortTestHelper.testSort(ShellSort.class, arr3);
        SortTestHelper.testSort(MergeSort.class, arr4);
        SortTestHelper.testSort(MergeSort.class, arr5, "sortBottomToUp");
    }

}
